package Leetcode.数组字符串;

/**
 * @Author: kirito
 * @Date: 2024/3/14 17:44
 * @Description:
 * 2789. 合并后数组中的最大元素
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个下标从 0 开始、由正整数组成的数组 nums 。
 *
 * 你可以在数组上执行下述操作 任意 次：
 *
 * 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
 * 返回你可以从最终数组中获得的 最大 元素的值。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [2,3,7,9,3]
 * 输出：21
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
 * - 选中 i = 1 ，得到数组 nums = [5,16,3] 。
 * - 选中 i = 0 ，得到数组 nums = [21,3] 。
 * 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
 * 示例 2：
 *
 * 输入：nums = [5,3,3]
 * 输出：11
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 1 ，得到数组 nums = [5,6] 。
 * - 选中 i = 0 ，得到数组 nums = [11] 。
 * 最终数组中只有一个元素，即 11 。
 *
 *
 * 首先理解题意，题目中的一次替换删除操作，其实是相当于将两个相邻并且非递减的数字进行求和合并。
 * 两个数字的和来替换掉原来的两个数字。而经过若干次这样的合并，整个数组的和是不变的。合并后数组中的每个元素，
 * 都是原数组的某个子数组的和，并且这些子数组拼接起来能构成整个原数组。为了使数组的最大值最大，
 * 我们可以贪心地做尽可能多的合并，直到整个数组都不能进行合并。合并的要求是后面的数字不小于前面的数字，
 * 我们就尽可能先合并靠后的数字，使其尽快能大，才能够合并前面的数字。
 *
 * 我们从后往前倒序遍历一次数组，依次比较两个相邻的元素，如果两个相邻的元素能够合并，就将其合并。如果不能合并，
 * 就继续往前判断。因为这样的操作流程，在比较过程中，靠后的数是所有操作流程可能性中能产生的最大值，而靠前的数，
 * 是所有操作流程可能性中能产生的最小值。如果在遍历过程中，比较的结果是不能合并，那么其他任何操作流程都无法合并这两个数。
 * 如果可以合并，那我们就贪心地合并，因为这样能使接下来的比较中，靠后的数字尽可能大。
 *
 */

public class maxArrayValue {
    /**
     * 这能想着反向遍历。。。。真想不出来。
     *
     * @param nums
     * @return
     */
    public long maxArrayValue(int[] nums) {
        long sum = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            sum = nums[i] <= sum ? nums[i] + sum : nums[i];
        }
        return sum;
    }
}
